import org.w3c.dom.Node;

import java.util.Deque;
import java.util.LinkedList;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-07-13
 * Time: 21:24
 */
//双向链表实现双端队列
public class DoubleLinkedListToDeQueue {
    public static class Node<V>{
        public V val;
        public Node<V> last;
        public Node<V> next;
        public Node(V val){
            this.val = val;
            last=null;
            next = null;
        }
    }
    public static  class MyDeQueue<V>{
        private Node<V> head;
        private Node<V> tail;
        private int size;
        
        public MyDeQueue(){
            head=null;
            tail=null;
            size=0;
        }
        
        //判空
        public boolean isEmpty(){
            return size==0;
        }
        //大小
        public int size(){
            return size;
        }
        
        //队头入，始终记住最终的头要在最左边，简记往中间挤
        public void pushHead(V val){
            Node<V> cur=new Node<>( val );
            if(head==null){
                head=cur;
                tail=cur;
            }else{
                //双端队列的插入和普通队列插入不一样
                //往中间挤
                cur.next=head;
                head.last=cur;
                head=cur;
            }
            size++;
        }
        //队尾入，记住尾最终要在最右边，所以插入新节点时尾结点的后继就是新节点，这样尾结点才能往右边走
        //简记往右边扩
        public void pushTail(V val) {
            Node<V> cur=new Node<>( val );
            if(head==null){
                head=cur;
                tail=cur;
            }else{
                //
                tail.next = cur;
                cur.last=tail;
                tail=cur;
            }
        }
        //队头出
        public V popHead (){
            V ret=null;
            if(head==null){
                return null;
            }
            size--;
            ret=head.val;
            if(head!=tail){
                head=head.next;
                //要把后继节点置为空，因为弹出去的就不用了
                head.last=null;
            }
            //如果减到head等于tail,那么tail也要置为空
            if(head==tail){
                head=null;
                tail=null;
            }
            return ret;
        }
        //队尾出
        public V popTail(){
            V ret=null;
            if(head==null){
                return null;
            }
            size--;
            ret=tail.val;
            //如果只有一个节点，那么弹出之后，就把head和tail置空
            if(head==tail){
                head=null;
                tail=null;
            }else{
                tail=tail.last;
                //next置空
                tail.next=null;
            }
            return ret;
        }
        //队头取元素
        public V peekHead(){
            V ret=null;
            if(head!=null){
                ret=head.val;
            }
            return ret;
        }
        //队尾取元素
        public V peekTail() {
            V ret = null;
            if ( tail != null ) {
                ret = tail.val;
            }
            return ret;
        }
    }
    public static void testDeque() {
        MyDeQueue<Integer> myDeque = new MyDeQueue<>();
        Deque<Integer> test = new LinkedList<>();
        int testTime = 5000000;
        int maxValue = 200000000;
        System.out.println("测试开始！");
        for (int i = 0; i < testTime; i++) {
            if (myDeque.isEmpty() != test.isEmpty()) {
                System.out.println("Oops!");
            }
            if (myDeque.size() != test.size()) {
                System.out.println("Oops!");
            }
            double decide = Math.random();
            if (decide < 0.33) {
                int num = (int) (Math.random() * maxValue);
                if (Math.random() < 0.5) {
                    myDeque.pushHead(num);
                    test.addFirst(num);
                } else {
                    myDeque.pushTail(num);
                    test.addLast(num);
                }
            } else if (decide < 0.66) {
                if (!myDeque.isEmpty()) {
                    int num1 = 0;
                    int num2 = 0;
                    if (Math.random() < 0.5) {
                        num1 = myDeque.popHead();
                        num2 = test.pollFirst();
                    } else {
                        num1 = myDeque.popTail();
                        num2 = test.pollLast();
                    }
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            } else {
                if (!myDeque.isEmpty()) {
                    int num1 = 0;
                    int num2 = 0;
                    if (Math.random() < 0.5) {
                        num1 = myDeque.peekHead();
                        num2 = test.peekFirst();
                    } else {
                        num1 = myDeque.peekTail();
                        num2 = test.peekLast();
                    }
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            }
        }
        if (myDeque.size() != test.size()) {
            System.out.println("Oops!");
        }
        while (!myDeque.isEmpty()) {
            int num1 = myDeque.popHead();
            int num2 = test.pollFirst();
            if (num1 != num2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束！");
    }
    
    public static void main(String[] args) {
        testDeque();
    }
}
